DSC 40B – Theoretical Foundations of Data Science II
Problems tagged with "best and worst case"
Problem #005
Tags: best and worst case
What is the best case time complexity of the following function in terms of \(n\)?
def foo(arr):
"""`arr` is a list containing n numbers."""
previous = None
n = len(arr)
for x in arr:
if x == previous:
for i in range(n**2):
print('Equal!')
return
previous = x
Solution
\(\Theta(n)\)
Problem #006
Tags: best and worst case
What is the worst case time complexity of the function in the previous problem?
Solution
\(\Theta(n^2)\)
Problem #018
Tags: best and worst case, mergesort
True or False: the best case time complexity of mergesort is \(\Theta(n)\).
Solution
False.
Problem #023
Tags: best and worst case
The below code takes in an array of numbers and returns the index of the first maximum. What is this code's best case time complexity?
def index_of_maximum(arr):
"""`arr` is an array with n elements."""
for i, x in enumerate(arr):
if x == max(arr):
return i
Solution
\(\Theta(n)\)
Problem #040
Tags: best and worst case
The below code takes in an array of numbers and returns the index of the first maximum.
def foo(arr):
"""`arr` is an array with n elements."""
for i, x in enumerate(arr):
if x == max(arr):
return i
What is the worst case time complexity of the function?
Solution
\(\Theta(n^2)\)
Problem #051
Tags: best and worst case
The code below takes in an array of \(n\) numbers and checks whether there is a pair of numbers in the array which, when added together, equal the maximum element of the array.
What is the best case time complexity of this code as a function of \(n\)? State your answer using asymptotic notation.
def exists_pair_summing_to_max(arr):
n = len(arr)
maximum = max(arr)
for i in range(n):
for j in range(i + 1, n):
if arr[i] + arr[j] == maximum:
return True
return False
Solution
\(\Theta(n)\)
Problem #067
Tags: best and worst case
What is the worst case time complexity of the function in the last problem? State your answer using asymptotic notation.
Solution
\(\Theta(n^2)\)
Problem #078
Tags: best and worst case
What is the best case time complexity of the following function in terms of \(n\)?
def foo(arr):
"""`arr` is a list containing n numbers."""
previous = None
n = len(arr)
for x in arr:
if x == previous:
for i in range(n**2):
print('Equal!')
return
previous = x
Solution
\(\Theta(n)\)
Problem #084
Tags: best and worst case
True or False: the best case time complexity of mergesort is \(\Theta(n)\).
Solution
False.
Problem #167
Tags: best and worst case
The code below takes in two lists, each containing \(n\) integers, and determines if the any number in the second list appears at least \(n/2\) times in the first list.
def boo(first_list, second_list):
"""first_list and second_list are both of size n"""
n = len(first_list)
for x in second_list:
count = 0
for y in first_list:
if x == y:
count += 1
if count >= n // 2:
return True
return False
print(boo([1, 6, 6, 4, 6], [6, 7, 8, 9, 10]))
Part 1)
What is the best case time complexity of this code as a function of \(n\)? State your answer using asymptotic notation.
Part 2)
What is the worst case time complexity of this code as a function of \(n\)? State your answer using asymptotic notation.
Solution
The best case is when the first element of the second list appears at least \(n/2\) times in the first list. In this case, the code will return True after iterating \(n/2\) times through the inner loop, taking \(\Theta(n)\) time total.
In the worst case, there is no element in the second list that appears \(n/2\) times in the first. We make all \(n\) iterations of the outer loop, and during each of the outer iterations, make \(n\) iterations of the inner loop, for a total of \(\Theta(n^2)\) time.
Problem #181
Tags: best and worst case, theoretical lower bounds
Consider the following problem: given two sorted lists, A and B, each containing \(n\) numbers, determine if the two lists share an element in common. That is, determine if there is a number \(x\) which appears in both lists.
Part 1)
What is a tight theoretical lower bound for this problem? Again, you may assume that the lists are both sorted. State your answer in asymptotic notation as a function of \(n\).
Part 2)
(2 points) Briefly (in 50 words or less) describe an algorithm for solving this problem and state its worst case time complexity. To earn full credit, you should give the optimal algorithm, but partial credit will be awarded for sub-optimal solutions. You may write pseudocode if you like, but an explanation in words is also sufficient. Make sure that you only state one algorithm!
Solution
Here's an approach that takes \(\Theta(n)\); it's similar to what we did in lecture for the movie problem.
Start with i = j = 0. If A[i] == A[j], return True, since you've found an element in common. If A[i] > A[j], increment j, otherwise increment i. Takes \(\Theta(n)\) time.
The brute force approach also earns credit: Loop over all pairs, checking if A[i] == B[j] for each pair. This takes \(\Theta(n^2)\) time.
Problem #191
Tags: best and worst case
The code below takes in two lists, each containing \(n\) integers.
def are_lists_equal(list1, list2):
if len(list1) != len(list2):
return False
for i in range(len(list1)):
if list1[i] != list2[j]:
return False
return True
def foo(list1, list2):
if are_lists_equal(list1, list2):
for i in list1:
print(i)
else:
for i in list1:
for j in list2:
for k in range(len(list1)):
print(i, j, k)
What is the best case time complexity of foo as a function of \(n\)? State your answer using asymptotic notation.
Solution
The best case is where the lists are equal. In this case the time complexity is \(\Theta(n)\). The worst case is when the lists are not equal in which case the time complexity is \(\Theta(n^3)\).